//给你一个整数 n 和一个二维整数数组 queries。 
//
// 有 n 个城市，编号从 0 到 n - 1。初始时，每个城市 i 都有一条单向道路通往城市 i + 1（ 0 <= i < n - 1）。 
//
// queries[i] = [ui, vi] 表示新建一条从城市 ui 到城市 vi 的单向道路。每次查询后，你需要找到从城市 0 到城市 n - 1 的最
//短路径的长度。 
//
// 返回一个数组 answer，对于范围 [0, queries.length - 1] 中的每个 i，answer[i] 是处理完前 i + 1 个查询后，
//从城市 0 到城市 n - 1 的最短路径的长度。 
//
// 
//
// 示例 1： 
//
// 
// 输入： n = 5, queries = [[2, 4], [0, 2], [0, 4]] 
// 
//
// 输出： [3, 2, 1] 
//
// 解释： 
//
// 
//
// 新增一条从 2 到 4 的道路后，从 0 到 4 的最短路径长度为 3。 
//
// 
//
// 新增一条从 0 到 2 的道路后，从 0 到 4 的最短路径长度为 2。 
//
// 
//
// 新增一条从 0 到 4 的道路后，从 0 到 4 的最短路径长度为 1。 
//
// 示例 2： 
//
// 
// 输入： n = 4, queries = [[0, 3], [0, 2]] 
// 
//
// 输出： [1, 1] 
//
// 解释： 
//
// 
//
// 新增一条从 0 到 3 的道路后，从 0 到 3 的最短路径长度为 1。 
//
// 
//
// 新增一条从 0 到 2 的道路后，从 0 到 3 的最短路径长度仍为 1。 
//
// 
//
// 提示： 
//
// 
// 3 <= n <= 500 
// 1 <= queries.length <= 500 
// queries[i].length == 2 
// 0 <= queries[i][0] < queries[i][1] < n 
// 1 < queries[i][1] - queries[i][0] 
// 查询中没有重复的道路。 
// 
//
// Related Topics 广度优先搜索 图 数组 👍 59 👎 0


package LeetCode.editor.cn;

import java.util.*;

/**
 * @author ldltd
 * @date 2024-11-19 23:51:08
 * @description 3243.新增道路查询后的最短距离 I
 */
public class ShortestDistanceAfterRoadAdditionQueriesI{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 ShortestDistanceAfterRoadAdditionQueriesI fun=new ShortestDistanceAfterRoadAdditionQueriesI();
	 	 Solution solution = fun.new Solution();
		  solution.shortestDistanceAfterQueries(5,new int[][]{{2,4},{0,2},{0,4}});
	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
		 //bfs 时间感人，而且计算出了每个点的最短。其实不需要
	//时间 O q*(n+q)  空间 O(n+q)
    public int[] shortestDistanceAfterQueries(int n, int[][] queries) {
        int [] res=new int[queries.length];
		List<Integer>[] g=new ArrayList[n];
		for (int i = 0; i < n-1; i++) {
			g[i]=new ArrayList<>();
			g[i].add(i+1);
		}
		g[n-1]=new ArrayList<>();
		int [] min=new int[n];
		Arrays.setAll(min, e->n+2);
		int i=0;
		for (int[] query : queries) {
			g[query[0]].add(query[1]);
			res [i++]=bfs(g,n,min);
		}
		return res;

    }
	private int bfs(List<Integer>[] g, int n, int[] min){
		Deque<int[]> q=new ArrayDeque<>();
		q.offer(new int[]{0,0});

		while (!q.isEmpty()){
			int[] poll = q.poll();
			for (Integer i : g[poll[0]]) {
				if(poll[1]+1<=min[i]){
					min[i]=poll[1]+1;
					q.offer(new int[]{i,poll[1]+1});
				}
			}
		}
		return min[n-1];
	}

	//动态规划
	//对于单向道路u,v 道路始终是递增的，且v>u
	//记录dp[i]表示到i的最短路径，用pre[i]表示到i的所有起点
	//则dp[i]=min dp[j]+1 其中j属于pre[i]
	//每次query。新增u v，只影响v以及他之后的，所以dp可以从v开始更新
	public int[] shortestDistanceAfterQueries1(int n, int[][] queries) {
		List<List<Integer>> pre=new ArrayList<>();
		for (int i = 0; i < n; i++) {
			pre.add(new ArrayList<>());
		}
		int[] dp=new int[n];
		for (int i = 1; i < n; i++) {
			pre.get(i).add(i-1);
			dp[i]=i;
		}
		int [] res=new int[queries.length];
		for (int i = 0; i < queries.length; i++) {
			pre.get(queries[i][1]).add(queries[i][0]);
			//从v开始更新
			for (int v = queries[i][1]; v < n; v++) {
				for (int u : pre.get(v)) {
					dp[v]=Math.min(dp[v],dp[u]+1);
				}
			}
			res[i]=dp[n-1];
		}
		return res;
	}

}
//leetcode submit region end(Prohibit modification and deletion)

}
